package number_operatation.nowcoder.easy;

/**
 * @author Stark
 * @description 不用加减乘除做加法
 * 题目链接:https://www.nowcoder.com/practice/e7e0d226f1e84ba7ab8b28efc6e1aebc?
 * tpId=8&&tqId=11065&rp=1&ru=/activity/oj&qru=/ta/cracking-the-coding-interview/question-ranking
 * @date 2022/4/27 20:20
 **/
public class UnusualAdd {
    int choice = 1;
    public int addAB(int A, int B) {
        //方法一
        if(choice == 1) {
            //表示正在处理的二进制位
            int a = 1;
            //保存加法的结果
            int num = 0;
            //条件:a大于A和B就结束
            while (a < A || a < B) {
                //num该二进制位为0
                if ((a & num) == 0) {
                    //A和B两个数对应a的二进制位都为1时
                    if ((a & A) != 0 && (a & B) != 0) {
                        //将a<<1的结果再或,表示两个1相加进位
                        num |= (a << 1);
                    }
                    //A和B该二进制位上只有一个1
                    else if ((a & A) != 0 || (a & B) != 0) {
                        //没有进位,直接或
                        num |= a;
                    }
                }
                //num该二进制位为1
                else {
                    //A和B该二进制位上都为1
                    if ((a & A) != 0 && (a & B) != 0) {
                        //将a<<1的结果再或,表示两个1相加进位
                        num |= (a << 1);
                    }
                    //A和B只有一个为1
                    else if ((a & A) != 0 || (a & B) != 0) {
                        //a取反和num相与保存其他位上的情况,再进位或
                        num = ((~a & num) | (a << 1));
                    }
                }
                a <<= 1;
            }
            return num;
        }

        //方法二
        if(choice == 2){
            int sum = A;
            int carry = 0;
            //判断条件是没有进位需要处理,此时sum就是两数相加
            while(B != 0){
                //如果没有进位，那么A 异或 B的结果就是两数相加的结果！！
                //如果有进位,那么carry就不为0
                //此时sum将不需要进位的值保留
                //让carry来处理进位
                sum = A ^ B;
                //两数相与,保存的是需要进位的位置,再左移一位就是最终进位
                carry = (A & B) << 1;
                A = sum;
                B = carry;
            }
        }
        return 0;
    }
}
